from typing import List


class Solution:
    """
    方法：动态规划，使用一维dp数组记录每个位置可以形成的最大正方形边长
    
    Args:
        matrix: List[List[str]], 由'0'和'1'组成的二维矩阵
        
    Returns:
        int: 矩阵中最大正方形的面积
        
    Time: O(m*n), m和n分别是矩阵的行数和列数
    
    Space: O(n), n是矩阵的列数
    """
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        max_side = 0
        dp = [0] * (n + 1)
        prev = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                temp = dp[j]
                if matrix[i-1][j-1] == '1':
                    dp[j] = min(dp[j], dp[j-1], prev) + 1
                    max_side = max(max_side, dp[j])
                else:
                    dp[j] = 0
                prev = temp
            prev = 0
        
        return max_side * max_side